package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 206. 反转链表
 * @date 2025/1/25 13:34
 */
public class E206 {

    /**
     * <h3>方法一：头插法</h3>
     *
     * @param head 链表头结点
     * @return 反转后的链表头结点
     */
    public ListNode reverseList1(ListNode head) {
        ListNode sentinel = new ListNode(-1);
        while (head != null) {
            ListNode temp = head.next;
            head.next = sentinel.next;
            sentinel.next = head;
            head = temp;
        }
        return sentinel.next;
    }

    /**
     * <h3>方法二：递归</h3>
     *
     * @param head 链表头结点
     * @return 反转后的链表头结点
     */
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
